/**
 * //中位数是有序列表中间的数。如果列表长度是偶数，中位数则是中间两个数的平均值。
 * //
 * // 例如，
 * //
 * // [2,3,4] 的中位数是 3
 * //
 * // [2,3] 的中位数是 (2 + 3) / 2 = 2.5
 * //
 * // 设计一个支持以下两种操作的数据结构：
 * //
 * //
 * // void addNum(int num) - 从数据流中添加一个整数到数据结构中。
 * // double findMedian() - 返回目前所有元素的中位数。
 * //
 * //
 * // 示例：
 * //
 * // addNum(1)
 * //addNum(2)
 * //findMedian() -> 1.5
 * //addNum(3)
 * //findMedian() -> 2
 * //
 * // 进阶:
 * //
 * //
 * // 如果数据流中所有整数都在 0 到 100 范围内，你将如何优化你的算法？
 * // 如果数据流中 99% 的整数都在 0 到 100 范围内，你将如何优化你的算法？
 * //
 * // Related Topics 设计 双指针 数据流 排序 堆（优先队列） 👍 605 👎 0
 */

package com.xixi.dataStructure.heap;

import java.util.Comparator;
import java.util.PriorityQueue;

public class ID00295FindMedianFromDataStream {
    public static void main(String[] args) {
        MedianFinder solution = new ID00295FindMedianFromDataStream().new MedianFinder();

        solution.addNum(2);
        System.out.println(solution.findMedian());
        solution.addNum(3);
        System.out.println(solution.findMedian());

    }


    //leetcode submit region begin(Prohibit modification and deletion)
    class MedianFinder {

        PriorityQueue<Integer> bigQueue; //大顶堆放前半部分
        PriorityQueue<Integer> smallQueue; //小顶堆放后半部分

        long count = 0L; //计数

        public MedianFinder() {
            this.smallQueue = new PriorityQueue<Integer>(new Comparator<Integer>() {
                @Override
                public int compare(Integer o1, Integer o2) {
                    return o1 - o2;
                }
            });

            this.bigQueue = new PriorityQueue<Integer>(new Comparator<Integer>() {
                @Override
                public int compare(Integer o1, Integer o2) {
                    return o2 - o1;
                }
            });
        }

        public void addNum(int num) {
            if(count == 0){
                ++count;
                this.bigQueue.offer(num);
            } else{
                ++count;
                int bigTop = this.bigQueue.peek();
                //小于等于bigTop，放到前半段，大于bigTop，放到后半段
                if(num <= bigTop){
                    this.bigQueue.offer(num);
                }else{
                    this.smallQueue.offer(num);
                }

                //判断两队列size差大于等于2的时候，需要重新调整队列，让两边的队列大小差小于2
                if(Math.abs(this.bigQueue.size() - this.smallQueue.size()) >=2){
                    if(this.bigQueue.size() > this.smallQueue.size()){
                        this.smallQueue.offer(this.bigQueue.poll());
                    }else{
                        this.bigQueue.offer(this.smallQueue.poll());
                    }
                }
            }



        }

        public double findMedian() {
            if(count == 0L) return 0.0;
            if(count%2 == 0){
                int bigTop = this.bigQueue.peek();
                int smallTop = this.smallQueue.peek();

                double result = ((double)bigTop + (double)smallTop)/2;
                return result;
            }else{
                if(this.bigQueue.size() > this.smallQueue.size()){
                    return this.bigQueue.peek();
                }else{
                    return this.smallQueue.peek();
                }
            }


        }
    }

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */
//leetcode submit region end(Prohibit modification and deletion)


}